/**
All functions in this module can be executed at compile time.

Macros:
  DECLREF = $(LINK2 #$1, $(D $1))
  TABLE_SV = <table border="1" cellpadding="4" cellspacing="0">
             <caption>Special Values</caption>
             $0</table>
 */
module ext.string;

import std.math;
import std.stdint;

import ext.functional;

version (unittest)
{
    import std.typetuple;
}


//===================================================================//
// General string functions
//===================================================================//

/*
Copy-on-write map function.
 */
private T[] mapCOW(alias map, T)(T[] arr) pure
    if (is(T == immutable))
{
    T[] marr;

    foreach (i, c; arr)
    {
        T mc = map(c);

        // copy on write
        if (mc != c && marr == null)
            marr = arr[0 .. i].idup;
        if (marr)
            marr ~= mc;
    }
    return marr ? marr : arr;
}

private char toAsciiUpper(char s) pure nothrow
{
    if ('a' <= s && s <= 'z')
        return s - ('a' - 'A');
    else
        return s;
}

private string toAsciiUpper(string s) pure
{
    return mapCOW!(toAsciiUpper)(s);
}


/***************************************
Returns true if $(D r) starts with $(D s).
 */
bool startsWith(string r, string s) pure nothrow
{
    if (r.length >= s.length)
        return r[0 .. s.length] == s;
    else
        return false;
}

unittest
{
    static assert( startsWith("", ""));
    static assert( startsWith("abc", ""));
    static assert( startsWith("abc", "a"));
    static assert( startsWith("abc", "abc"));
    static assert(!startsWith("ab", "abc"));
    static assert(!startsWith("ab", "c"));
    static assert(!startsWith("", "a"));
}


/***************************************
Returns the leading substring of $(D r), all bytes in which satisfy
the predicate $(D pred).

Example:
--------------------
assert(span!isDigit("0123456789abcdef") == "0123456789");
--------------------
 */
string span(alias pred)(string r) pure nothrow
{
    foreach (i, e; r)
    {
        if (!pred(e))
            return r[0 .. i];
    }
    return r;
}

unittest
{
    static bool isDigit(char ch) pure nothrow
    {
        return '0' <= ch && ch <= '9';
    }
    static assert(span!isDigit("") == "");
    static assert(span!isDigit("a") == "");
    static assert(span!isDigit("11") == "11");
    static assert(span!isDigit("11a") == "11");
}


//===================================================================//
// Convertion between number & string
//===================================================================//

private
{
    static immutable char[36] BASE36_ENCODE =
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    typedef ubyte Decode = ubyte.max;

    static immutable Decode[char.max + 1] BASE36_DECODE =
        [ '0':  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
          'A': 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
               20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
               30, 31, 32, 33, 34, 35 ];
}

private template RadixPolicy(uint radix)
    if (1 <= radix && radix <= 36)
{
    enum uint RADIX = radix;

    bool isDigit(char c) pure nothrow
    {
        return BASE36_DECODE[c] < RADIX;
    }

    ubyte decode(char c) pure nothrow
    in
    {
        assert(isDigit(c));
    }
    body
    {
        return BASE36_DECODE[c];
    }

    char encode(ubyte n) pure nothrow
    in
    {
        assert(n < RADIX);
    }
    body
    {
        return BASE36_ENCODE[n];
    }
}

// Common radices
private
{
    alias RadixPolicy!( 2) Binary;
    alias RadixPolicy!( 8) Octal;
    alias RadixPolicy!(10) Decimal;
    alias RadixPolicy!(16) Hexadecimal;
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// number -> string
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns a decimal string representing the given signed or unsigned
integer $(D num).

The decimal string consists of a possible negative sign $(D -)
followed by a sequence of decimal digits.
 */
string toString(intmax_t num) pure nothrow
{
    if (num < 0)
        return "-" ~ toString(cast(uintmax_t) -num);
    else
        return       toString(cast(uintmax_t)  num);
}

unittest
{
    static bool test(string n)()
    {
        // [workaround] signed integer overflow (-9223372036854775808)
        enum v = cast(intmax_t) mixin(n ~ "UL");
        return toString(v) == n;
    }
    static assert(test!("0")());
    static assert(test!( "2147483647")());
    static assert(test!("-2147483648")());
    static assert(test!( "9223372036854775807")());
    static assert(test!("-9223372036854775808")());
}

/**
Ditto
 */
string toString(uintmax_t num) pure nothrow
{
    string s;
    for (uintmax_t x = num; x != 0; x /= 10)
    {
        const dig = cast(char) ('0' + x % 10);
        s = dig ~ s;
    }
    return num ? s : "0";
}

unittest
{
    static bool test(string n)()
    {
        return toString(mixin(n ~ "UL")) == n;
    }
    static assert(test!("0")());
    static assert(test!("4294967295")());
    static assert(test!("18446744073709551615")());
}


/***************************************
Returns a hexadecimal string representing the given signed or unsigned
integer $(D num).

The hexadecimal string starts with a possible negative sign $(D -), and
the rest of the string consists of the hexadecimal prefix $(D 0x)
followed by at least $(D mincol) uppercase hexadecimal digits.
 */
string toHexString(intmax_t num, uint mincol = 1) pure nothrow
{
    if (num < 0)
        return "-" ~ toHexString(cast(uintmax_t) -num, mincol);
    else
        return       toHexString(cast(uintmax_t)  num, mincol);
}

unittest
{
    static bool test(string n)(uint mc)
    {
        return toHexString(cast(intmax_t) mixin(n), mc) == n;
    }
    static assert(test!("-0x1")(1));
    static assert(test!("-0xFFFF")(2));
    static assert(test!("-0x0123456789ABCDEF")(16));
    static assert(test!("-0x8000000000000000")(16));
}

/**
Ditto
 */
string toHexString(uintmax_t num, uint mincol = 1) pure nothrow
{
    string s = "0x";
    bool hizero = true;

    foreach_reverse (i; 0 .. uintmax_t.sizeof * 2)
    {
        const digit = cast(ubyte) ((num >> (i * 4)) & 0xF);
        if (hizero && digit == 0 && i >= mincol)
            continue;
        s ~= Hexadecimal.encode(digit);
        hizero = false;
    }
    return s;
}

unittest
{
    static bool test(string n)(uint mc)
    {
        return toHexString(cast(uintmax_t) mixin(n), mc) == n;
    }
    static assert(test!("0x0")(1));
    static assert(test!("0xFFFF")(2));
    static assert(test!("0x0123456789ABCDEF")(16));
    static assert(test!("0xFFFFFFFFFFFFFFFF")(16));
}


/***************************************
Returns a hexadecimal string representing the given floating point
value $(D num).

The hexadecimal string starts with a possible negative sign $(D -), and
the rest of the string consists of the hexadecimal prefix $(D 0x)
followed by a significand part and then an exponent part. The
significand part is $(D 0) if the represented number is zero; otherwise
it consists of an integer part $(D 1) followed by an optional fraction
part, which consists of a decimal point $(D .) followed by a sequence
of uppercase hexadecimal digits. The exponent part consists of a prefix
$(D p) followed by a decimal signed integer.

$(TABLE_SV
  $(TR $(TH $(D num))
       $(TH $(D toHexString(num))))
  $(TR $(TD NaN)
       $(TD $(D_STRING "NaN")))
  $(TR $(TD +&infin;)
       $(TD $(D_STRING "Infinity")))
  $(TR $(TD &minus;&infin;)
       $(TD $(D_STRING "-Infinity")))
)

Example:
--------------------
enum real pi = 3.1415926535897932385;

// toHexString is executable at compile time.
enum string hex = toHexString(pi);
static assert(hex == "0x1.921FB54442D18468p1");

// The returned string is a valid hexadecimal floating constant.
static assert(mixin(hex) == pi);
--------------------
 */
string toHexString(real num) pure nothrow
{
    // Handle special values.
    if (num !<>= 0) return "NaN";
    if (num == 0) return "0x0p0";
    if (num < 0) return "-" ~ toHexString(-num);
    if (num == real.infinity) return "Infinity";

    // x is now positive finite.
    real x = num;
    assert(0 < x && x < real.infinity);

    /* Extract the exponent part. After that, the exponent of x will
     * be reduced to zero (therefore 1 <= x < 2).
     */
    int exp = 0;

    version (BUILTIN_FREXP)
    {
        x = frexp(x, exp);
    }
    else
    {
        while (x <  0x1p-511) { x *= 0x1p+512; exp -= 512; }
        while (x >= 0x1p+512) { x *= 0x1p-512; exp += 512; }
        while (x <  0x1p-31) { x *= 0x1p+32; exp -= 32; }
        while (x >= 0x1p+32) { x *= 0x1p-32; exp += 32; }
        while (x <  0x1p-0) { x *= 0x1p+1; --exp; }
        while (x >= 0x1p+1) { x *= 0x1p-1; ++exp; }
    }
    assert(1 <= x && x < 2);

    /* Convert the significand part to a hexadecimal string. The
     * integer part is always 1 since x is nonzero.
     */
    string mant = "1";
    x -= 1;
    assert(0 <= x && x < 1);

    // Handle the fraction part.
    if (x != 0)
    {
        mant ~= ".";
        do
        {
            x *= 0x1p4; // shift up by 4-bits

            const dig = cast(int) x;
            mant ~= Hexadecimal.encode(cast(ubyte) dig);
            x    -= dig;
        }
        while (x != 0);
    }

    return "0x" ~ mant ~ "p" ~ toString(cast(intmax_t) exp);
}

unittest
{
    static assert(toHexString(real.nan) == "NaN");
    static assert(toHexString(+real.infinity) ==  "Infinity");
    static assert(toHexString(-real.infinity) == "-Infinity");
    static assert(toHexString(0.0L) == "0x0p0");

    alias TypeTuple!(
            "0x1p0", "0x1p512", "0x1p-512", "0x1p1023", "0x1p-1023",
            "0x1.2345678p9", "0x1.ABCDEFp0", "0x1.369CFp42",
            "0x1.FFFFFFFFFFFEp0") tab;
    foreach (i, s; tab)
    {
        enum p = tab[i];
        enum n = "-" ~ p;
        static assert(toHexString(mixin(p ~ "L")) == p);
        static assert(toHexString(mixin(n ~ "L")) == n);
    }

    static if (real.max_exp == 1 << 15 && real.mant_dig == 64)
    {
        enum max = "0x1.FFFFFFFFFFFFFFFEp16383";
        static assert(toHexString(mixin(max ~ "L")) == max);
    }

    // the smallest representable denormal value
    enum dxp = real.min_exp - real.mant_dig;
    enum den = "0x1p" ~ toString(cast(intmax_t) dxp);
    static assert(toHexString(mixin(den ~ "L")) == den);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// string -> number
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns the signed (unsigned) integer represented by the given valid
binary, octal, decimal or hexadecimal string $(D str).

Throws:
$(UL
  $(LI $(D Exception) if $(D str) is invalid)
  $(LI $(D Exception) on integer overflow)
)

Example:
--------------------
intmax_t num = toInt("-0xDD");
assert(num == -221);
--------------------
 */
intmax_t toInt(string str) pure
{
    if (str.length == 0)
        throw new Exception("digit is expected");

    if (str[0] == '+')
        return toInt(str[1 .. $]);

    /* We handle a sign and digits separately, and use toUint for
     * parsing the digits. Note that the result of toUint may cause
     * integer overflow when being converted to a signed integer.
     */
    string rem = str;

    const neg = (rem[0] == '-');
    if (neg)
        rem = rem[1 .. $];

    const u = toUint(rem);

    // Check for integer overflow. Notice the axiom: -min = max+1.
    const bound = cast(uintmax_t) intmax_t.max + (neg ? 1 : 0);
    if (u > bound)
        throw new Exception("signed integer overflow");

    const i = cast(intmax_t) u;
    return neg ? -i : i;
}

unittest
{
    static assert(toInt("0") == 0);
    static assert(toInt("42") == 42);
    static assert(toInt("-42") == -42);
    static assert(toInt(toString(intmax_t.max)) == intmax_t.max);
    static assert(toInt(toString(intmax_t.min)) == intmax_t.min);

    // overflow
    enum n = cast(uintmax_t) intmax_t.max + 1;
    static assert(throws!toInt(      toString(n    )));
    static assert(throws!toInt("-" ~ toString(n + 1)));
}


/**
Ditto
 */
uintmax_t toUint(string str) pure
{
    if (str.length == 0)
        throw new Exception("digit expected");

    const upstr = toAsciiUpper(str);

    if (startsWith(upstr, "0X"))
        return toUintX!Hexadecimal(upstr[2 .. $]);

    if (startsWith(upstr, "0B"))
        return toUintX!Binary(upstr[2 .. $]);

    if (startsWith(upstr, "0") && upstr.length > 1)
        return toUintX!Octal(upstr[1 .. $]);

    return toUintX!Decimal(upstr);
}

unittest
{
    static assert(toUint("0xABC_DEF") == 0xABCDEF);
    static assert(toUint("0Xfed_cba") == 0xFEDCBA);
    static assert(toUint("0b110_010") == 0b110010);
    static assert(toUint("0B010_011") == 0b010011);
    static assert(toUint("0_777") == 0777);
    static assert(toUint("42") == 42);
    static assert(toUint("0") == 0);

    enum max = toString(uintmax_t.max);
    static assert(toUint(max) == mixin(max ~ "UL"));

    // overflow
    static assert(throws!toUint(toString(uintmax_t.max) ~ "0"));

    static if (is(uintmax_t == ulong))
        static assert(throws!toUint("18446744073709551616"));

    // malformed strings
    static assert(throws!toUint("0xG"));
    static assert(throws!toUint("0b2"));
    static assert(throws!toUint("08"));
    static assert(throws!toUint("4.2"));
}


/*
[internal]
 */
private uintmax_t toUintX(alias Base)(string str) pure
in
{
    assert(str.length);
}
body
{
    uintmax_t num = 0;

    foreach (c; str)
    {
        if (c == '_')
            continue; // separator
        const uc = toAsciiUpper(c);

        if (!Base.isDigit(uc))
            throw new Exception("unexpected digit");
        const save = num;
        num *= Base.RADIX;
        num += Base.decode(uc);

        if (num < save)
            throw new Exception("integer overflow");
    }
    return num;
}


/***************************************
Returns the floating point value represented by the given valid decimal
or hexadecimal string $(D str). $(D str) can be one of the special
values described in $(DECLREF toHexString).

Throws:
$(UL
  $(LI $(D Exception) if $(D str) is not a valid decimal nor
       hexadecimal floating string.)
  $(LI $(D Exception) on exponent overflow)
)

Example:
--------------------
real num = toReal("0x3.243F6A8885A308Dp0");
assert(num == 3.1415926535897932385);
--------------------
 */
real toReal(string str) pure
{
    if (str.length == 0)
        throw new Exception(
            "string does not represent a valid floating point value");

    // for case-insensitive comparison
    const upstr = toAsciiUpper(str);

    if (upstr == "NAN")
        return real.nan;

    if (str[0] == '-')
        return -toReal(str[1 .. $]);

    if (upstr == "INFINITY")
        return real.infinity;

    if (startsWith(upstr, "0X"))
        return toRealX!Hexadecimal(upstr[2 .. $], 'P', 2);

    return toRealX!Decimal(upstr, 'E', 10);
}

unittest
{
    static bool eq(real a, real b) pure nothrow
    {
        const r = a - b;
        return (r < 0 ? -r : r) < (real.epsilon * 10);
    }

    // Special values
    enum n0 = toReal("0");
    static assert(n0 == 0);

    enum nan = toReal("NaN");
    static assert(nan !<>= 0);

    enum pinf = toReal("Infinity");
    static assert(pinf == real.infinity);

    enum ninf = toReal("-Infinity");
    static assert(ninf == -real.infinity);

    // decimal floats can be inexact
    enum n1 = toReal("42");
    static assert(eq(n1, 42));

    enum n2 = toReal("-.31830988618379067154");
    static assert(eq(n2, -.31830988618379067154));

    enum n3 = toReal("3.1415926535897932385");
    static assert(eq(n3, 3.1415926535897932385));

    // with decimal exponent
    enum n4 = toReal("42e42");
    static assert(eq(n4, 42e42));

    enum n5 = toReal("-.0031830988618379067154E2");
    static assert(eq(n5, -.0031830988618379067154E2));

    enum n6 = toReal("314.15926535897932385e-2");
    static assert(eq(n6, 314.15926535897932385e-2));

    // hexadecimal floats must be exact
    enum n7 = toReal("0xDDp2");
    static assert(n7 == 0xDDp2);

    enum n8 = toReal("-0x.aaaaP-2");
    static assert(n8 == -0x.aaaaP-2);

    enum n9 = toReal("0x19.21FB54442D18468p-3");
    static assert(n9 == 0x19.21FB54442D18468p-3);

    // embedded separators are ignored
    enum n10 = toReal("0x_1_._2_p_3_");
    static assert(n10 == 0x1.2p3);

    enum n11 = toReal("0x_1_.___p_3_");
    static assert(n11 == 0x1p3);

    enum n12 = toReal("0x___._2_p_3_");
    static assert(n12 == 0x.2p3);

    // unexpected characters
    static assert(throws!toReal("1.0p4"));
    static assert(throws!toReal("1.abcd"));
    static assert(throws!toReal("0xGG"));
    static assert(throws!toReal("1.0e4a"));
    static assert(throws!toReal("0x1.0p4a"));

    // no significand
    static assert(throws!toReal(""));
    static assert(throws!toReal("e0"));
    static assert(throws!toReal("_e0"));
    static assert(throws!toReal("_.e0"));
    static assert(throws!toReal("._e0"));
    static assert(throws!toReal("_._e0"));

    // denormal
    enum dxp = real.min_exp - real.mant_dig;
    enum den = "0x1p" ~ toString(cast(intmax_t) dxp);
    static assert(0 < toReal(den) && toReal(den) < real.min);

    // overflow
    enum of = "0x1p" ~ toString(cast(intmax_t) real.max_exp + 1);
    static assert(throws!toReal(      of));
    static assert(throws!toReal("-" ~ of));
}


// [internal]
private real toRealX(alias Base)(
        string str, char expchar, uint expbase) pure
out(r)
{
    assert(r <>= 0);
    assert(abs(r) <= real.max);
    assert(expbase >= 1);
}
body
{
    string rem = str;
    real   num = 0;

    /* We first build a mantissa as a pure decimal fraction, regardless
     * of the actual position of the decimal point; and we will fix the
     * position of the decimal point later.
     */
    real weight = 1; // place weight for each figure
    uint intfigs;    // number of figures in the integer part
    uint fracfigs;   // number of figures in the fraction part
    bool infrac;     // true in the fraction part

    while (rem.length && rem[0] != expchar)
    {
        // embedded separator
        if (rem[0] == '_')
        {
            rem = rem[1 .. $];
            continue;
        }

        // count the number of figures
        if (!infrac)
        {
            if (rem[0] == '.')
            {
                infrac = true;
                rem = rem[1 .. $];
                continue;
            }
            ++intfigs;
        }
        else
        {
            ++fracfigs;
        }

        // read in a figure
        const fig = rem[0];
        if (!Base.isDigit(fig))
            throw new Exception("unexpected digit");
        rem = rem[1 .. $];

        weight *= 1.L / Base.RADIX;
        num    += Base.decode(fig) * weight;
    }

    if (intfigs + fracfigs == 0)
        throw new Exception("significand is empty");

    // Fix the position of the decimal point.
    num *= pow(cast(real) Base.RADIX, intfigs);

    /* Parse the remaining string as the exponent. It is a decimal
     * string, so we use the toInt for parsing it. Beware of overflow!
     */
    if (rem.length)
    {
        if (rem[0] != expchar)
            throw new Exception("exponent is expected");
        rem  = rem[1 .. $];
        num *= pow(cast(real) expbase, toInt(rem));
    }

    if (abs(num) > real.max)
        throw new Exception("floating point overflow");

    return num;
}


/*
[workaround] cannot evaluate std.math.pow at compile time
 */
private real pow(real num, intmax_t exp) pure nothrow
{
    if (exp < 0)
        // use 1/num (rather than 1/pow) to allow denormal result
        return pow(1 / num, -exp);

    real mult = num;
    real p    = 1;
    for (intmax_t r = exp; r != 0; r >>= 1)
    {
        if (r & 1)
            p *= mult;
        mult *= mult;
    }
    return p;
}

// ditto
private real pow(real num, uint exp) pure nothrow
{
    return pow(num, cast(intmax_t) exp);
}

unittest
{
    static assert(pow(0x1p+1L, cast(intmax_t) +42) == 0x1p+42);
    static assert(pow(0x1p+1L, cast(intmax_t) -42) == 0x1p-42);
    static assert(pow(0x1p-1L, cast(intmax_t) +42) == 0x1p-42);
    static assert(pow(0x1p-1L, cast(intmax_t) -42) == 0x1p+42);

    // denormal
    enum dxp = real.min_exp - real.mant_dig;
    enum den = pow(0x1p1L, cast(intmax_t) dxp);
    static assert(den > 0);
    assert(!isNormal(den));
}


